package 剑指offer;

import java.util.HashSet;
import java.util.Set;

/**
 * @author: tyy 剑指 Offer
 * 575. 分糖果
 * Alice 有 n 枚糖，其中第 i 枚糖的类型为 candyType[i] 。Alice 注意到她的体重正在增长，所以前去拜访了一位医生。
医生建议 Alice 要少摄入糖分，只吃掉她所有糖的 n / 2 即可（n 是一个偶数）。Alice 非常喜欢这些糖，她想要在遵循医生建议的情况下，尽可能吃到最多不同种类的糖。
给你一个长度为 n 的整数数组 candyType ，返回： Alice 在仅吃掉 n / 2 枚糖的情况下，可以吃到糖的最多种类数。
示例 1：
输入：candyType = [1,1,2,2,3,3]
输出：3
解释：Alice 只能吃 6 / 2 = 3 枚糖，由于只有 3 种糖，她可以每种吃一枚。
 * @create: 2021-10-31 17:40
 * @description:
 **/
public class Solution13 {
    public int distributeCandies(int[] candyType) {
        Set<Integer> set = new HashSet<>();
        for (int c: candyType) set.add(c);
        return Math.min(set.size(), candyType.length>>1);

        // 使用set,记住求唯一用set集合
        /*int length = candyType.length;
        int num = length / 2;
        Set<Integer> set = new HashSet<>();
        for(int i : candyType){
            set.add(i);
        }
        return set.size() > num ? num : set.size();*/

        // 使用list
        /*List list = new ArrayList();
        // 获取数组中不同元素的个数
        for (int i = 0; i < length; i++) {
            int candy = candyType[i];
            if (!list.contains(candy)) {
                list.add(candy);
            }
        }
        return list.size() > num ? num : list.size();*/
    }
    public static void main(String[] args) {
        int candyType[] = {6,6,6,6,1,2,3,4};
        int integers = new Solution13().distributeCandies(candyType);

        System.out.println("integers = " + integers);
    }
}